#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void printfArray(int *array, int length) {
    for (int i = 0; i < length; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

void bucketSort(int *array, int length) {
    int min_value;
    int max_value;

    bool flag = true;
    for (int i = 0; i < length; i++) {
        if (flag) {
            min_value = max_value = array[i];
            flag = false;

        } else {
            min_value = min(min_value, array[i]);
            max_value = max(max_value, array[i]);
        }
    }

    int bucket_size = sqrt(max_value - min_value) + 1;
    int bucket_count = (max_value - min_value) / bucket_size + 1;

    vector<int> bucket[bucket_count];

    for (int i = 0; i < length; ++i) {
        int index = min(bucket_count - 1, (array[i] - min_value) / bucket_size + 1);

        bucket[index].push_back(array[i]);
    }

    for (int i = 0; i < bucket_count; ++i) {
        sort(bucket[i].begin(), bucket[i].end());
    }

    int count = 0;
    for (int i = 0; i < bucket_count; ++i) {
        for (int const &value : bucket[i]) {
            array[count++] = value;
        }
    }
}
int main() {


    int array[] = {10, 2, 4, 6, 12, 7, 3, 25, 11, 12, 2, 15, 11, 6, 7, 12, 2, 44, 12, 1, 4, 11, 6, 17, 19, 0, 8};
    int length = (sizeof(array) / sizeof(int));
    cout << "length = " << length << endl;

    cout << "排序前: ";
    printfArray(array, length);

    bucketSort(array, length);

    cout << "排序后: ";
    printfArray(array, length);

    return 0;
}